package javax;

public class Xp_0109 {
    //快排
    //原始快排
    public static int sort1(int[] arr,int L , int R){
        //划分值
        int p = arr[R];
        //小于等于区右边界值
        int less = L-1;
        for (int i = L;i<=R ; i++){
            if (arr[i]<=p){
               //swap(arr,less + 1 ,i)  -> swap(arr,++less,i)
                XpUtils.swap(arr,++less,i);
            }
        }
        return less;
    }
    //改进版外排、荷兰国旗问题
    public static int[] sort2(int[] arr,int L ,int R){
        //小于区
        int less = L-1 ;
        //大于区包括了比较值  int p = arr[R+1]  more = R+1
        int more = R ;
        while (L<more){
            if (arr[L]<arr[R]){
                XpUtils.swap(arr,++less,L++);
            }else if (arr[L]>arr[R]){
                XpUtils.swap(arr,--more,L);
            }else {
                L++;
            }
        }
        //将比较值换回应该所在的位置
        XpUtils.swap(arr,more,R);
        return new int[]{less + 1,more};
    }
    public static void main(String []args){
        int[] test = {3,2,4,5,7,6};
        /*int sort1 = sort1(test, 0, test.length -1);
        for (int i =0 ;i<test.length ;i++){
            System.out.print(test[i]);
        }
        System.out.println();
        System.out.println(sort1);*/
        int[] ints = sort2(test, 0, test.length - 1);
        XpUtils.print(ints);
        System.out.println();
        System.out.println(ints[0]);
        System.out.println(ints[1]);
    }
}
